package com.ljx.SlidingWindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author 李加喜
 * @Package com.ljx.SlidingWindow
 * @date 2021-11-10 11:25
 */

/**
 * 查询找所有字母异位词
 */
public class FindZiChuan {
    public static void main(String[] args) {

    }
    public List<Integer> findAnagrams(String s, String p) {
        HashMap<Character, Integer> need = new HashMap<>(16);
        HashMap<Character, Integer> window = new HashMap<>(16);
        ArrayList<Integer> indexList = new ArrayList<>();
        char[] ps = p.toCharArray();
        for (char pp:ps){
            need.put(pp,need.getOrDefault(pp,0)+1);
        }
        int left=0,right=0;
        // 记录当前数量
        int valid=0;
        char[] ss = s.toCharArray();
        for (int i=0;i<ss.length;i++){
            char c=ss[i];
            right++;
            // 更新窗口的内容
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            if (right-left>=ps.length){
                if (valid==need.size()){
                    indexList.add(left);
                }
                char d=ss[left];
                left++;
                if ( need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
        }
        return indexList;
    }
}
